#!/usr/bin/perl

use strict;
use Storable qw(dclone);
use Data::Dumper;
use Math::Combinatorics;
use SQL::Statement;

# partitioning attribute
my %tablepartkey = (
  "b" => "range:id",
  "c" => "range:id",
  "d" => "range:sid",
  "e" => "range:fid"
);

# tables to partitions
my %table2parts = (
  "b" => [ "b1", "b2" ],
  "c" => [ "c1", "c2" ],
  "d" => [ "d1", "d2" ], 
  "e" => [ "e1", "e2" ] 
);

# partitions to tables
my %part2table = (
    "b1" => "b",
    "b2" => "b",
    "c1" => "c",
    "c2" => "c",
    "d1" => "d",
    "d2" => "d",
    "e1" => "e",
    "e2" => "e"
);

# partitions to partitioning attribute range
my %part2range = ( 
  "b1" => [0, 5], 
  "b2" => [6, 10],
  "c1" => [0, 5], 
  "c2" => [6, 10],
  "d1" => [0, 10],
  "d2" => [11, 20],
  "e1" => [21, 30],
  "e2" => [31, 40]
);

# partition replicas
my %part2repl = ( 
  "b1" => ["urlb1-1", "urlb1-2"],
  "b2" => ["urlb2-1", "urlb2-2"],
  "c1" => ["urlc1-1", "urlc1-2"],
  "c2" => ["urlc2-1", "urlc2-2"],
  "d1" => ["urld1-1", "urld1-2"],
  "d2" => ["urld2-1", "urld2-2"]
);

## SQL Statements

#my $sql = "SELECT a FROM b WHERE e=7 ORDER BY f DESC LIMIT 5,2";
#my $sql = "SELECT a FROM b WHERE id=9 and e=7 ORDER BY f DESC LIMIT 5,2";
#my $sql = "SELECT a FROM b, c WHERE b.id=c.id AND b.e=7 ORDER BY f DESC LIMIT 5,2";
#my $sql = "SELECT a FROM b, c, d WHERE b.id=c.id AND c.sid=d.sid AND d.id=7 ORDER BY f DESC LIMIT 5,2";
#my $sql = "SELECT a FROM b, c, d WHERE e=7 AND b.id=c.id OR 1=1 AND c.sid=d.sid";
my $sql = "SELECT a FROM b, c, d WHERE b.id=c.id AND b.id=c.sid";
#my $sql = "SELECT a FROM b, c, d WHERE b.id=c.id AND c.sid=d.sid AND b.id>5";
#my $sql = "SELECT a FROM b, c, d, e WHERE b.id=c.id AND c.sid=d.sid AND d.fid=e.fid";
#my $sql = "SELECT a FROM b, c, d, e WHERE b.id=c.id AND b.id=d.sid AND b.id=e.fid";

# parse the sql statement
my $p = SQL::Parser->new();
$p->{RaiseError}=1;
$p->{PrintError}=0;
my $stmt = SQL::Statement->new($sql,$p);

print Dumper $stmt->where();
my @tables = $stmt->tables();
print $tables[0]->name();
exit;

my $tables = $stmt->{"table_names"};
my @subqueries=();

print "$sql\n\n";

if(scalar(@$tables) == 1) {     # single table query
  my $tablename = $tables->[0];
  foreach my $partition (@{$table2parts{$tablename}}) {
    my %subquery = (
      "select" => dclone($stmt->{"org_col_names"}),
      "from" => [$partition],
      "where" => dclone($stmt->{"where_clause"})
    );
    partitionizeSubquery($tablename, $partition, \%subquery);
    push @subqueries, \%subquery;
  }
} else {                        # multi table query
  # get the number of partitions for each table
  my @npart = ();
  foreach my $tablename (@$tables) {
    push @npart, scalar(@{$table2parts{$tablename}});
  }

  my @allcomb = ();
  getAllCombinations(\@npart, 0, "", \@allcomb);

  # map each combination string to a subquery
  foreach my $combstr (@allcomb) {
    my %baseSubquery = (
      "select" => dclone($stmt->{"org_col_names"}),
      "from" => dclone($stmt->{"table_names"}),
      "where" => dclone($stmt->{"where_clause"})
    );
    my @partidx = split(/\,/, $combstr);

    for(my $i = 0; $i < scalar(@$tables); $i++) {
      my $tablename = $tables->[$i];
      my $partname = $table2parts{$tablename}->[$partidx[$i]];
      partitionizeSubquery($tablename, $partname, \%baseSubquery);
    }
    
    push @subqueries, \%baseSubquery;
  }
}


print scalar(@subqueries)." subqueries generated\n";
eliminateSubqueries(\@subqueries);
print scalar(@subqueries)." subqueries remaining after elimination\n";

# enumerate the subquery plans

# get pointers to all of the joins
foreach my $sq (@subqueries) {
  my @joins = ();
  getJoins($sq->{"where"}, \@joins);

  my @subtrees = enumerateSubqueries(\@joins);
  #print Dumper \@subtrees;
}

sub enumerateSubqueries {
  my ($edges) = @_;
  my @results = ();
 
  if (scalar(@$edges) == 0) {
    return @results;
  } 

  if (scalar(@$edges) == 1) {
    push @results, dclone($edges->[0]);
    return @results;
  } 

  foreach my $e (@$edges) {
    my %root = ();
    my @L = ();
    my @R = ();
    my @excluded = ($e);

    findLeft(\@L, $edges, $e, \@excluded);
    findRight(\@R, $edges, $e, \@excluded);

    my @left = enumerateSubqueries(\@L);
    my @right = enumerateSubqueries(\@R);
  
    if (scalar(@left) == 0) {
      $root{"arg1"} = $e->{"arg1"};
      foreach my $rtree (@right) {
        $root{"arg2"} = $rtree;
        push @results, dclone(\%root);
      }
    } elsif (scalar(@right) == 0) {
      $root{"arg2"} = $e->{"arg2"};
      foreach my $ltree (@left) {
        $root{"arg1"} = $ltree;
        push @results, dclone(\%root);
      }
    } else {
      foreach my $tree (@left) {
        $root{"arg1"} = $tree;
        foreach my $tree2 (@right) {
          $root{"arg2"} = $tree2;
          push @results, dclone(\%root);
        }
      }
    }
  }

  return @results;
}

sub findLeft {
  my ($left, $edges, $e, $excluded) = @_;

  my ($et1, ) = split(/\./, $e->{"arg1"}->{"value"});
  foreach my $tmpedge (@$edges) {
    my $flag = 0;
    if ($e == $tmpedge) {next;}
    foreach my $ex (@$excluded) {
      if($tmpedge == $ex) {$flag = 1;}
    }
    if($flag) {next;}
    my ($t1, ) = split(/\./, $tmpedge->{"arg1"}->{"value"});
    my ($t2, ) = split(/\./, $tmpedge->{"arg2"}->{"value"});
    if($t1 eq $et1 || $t2 eq $et1) {
      push @$left, $tmpedge;
      push @$excluded, $tmpedge;
      findLeft($left, $edges, $tmpedge, $excluded);
      findRight($left, $edges, $tmpedge, $excluded);
    }
  }
}

sub findRight {
  my ($right, $edges, $e, $excluded) = @_;

  my ($et2, ) = split(/\./, $e->{"arg2"}->{"value"});
  foreach my $tmpedge (@$edges) {
    my $flag = 0;
    if ($e == $tmpedge) {next;}
    foreach my $ex (@$excluded) {
      if($tmpedge == $ex) {$flag = 1;}
    }
    if($flag) {next;}
    my ($t1, ) = split(/\./, $tmpedge->{"arg1"}->{"value"});
    my ($t2, ) = split(/\./, $tmpedge->{"arg2"}->{"value"});
    if($t1 eq $et2 || $t2 eq $et2) {
      push @$right, $tmpedge;
      push @$excluded, $tmpedge;
      findLeft($right, $edges, $tmpedge, $excluded);
      findRight($right, $edges, $tmpedge, $excluded);
    }
  }
}

sub getJoins {
  my ($cond, $result) = @_;
  if (exists $cond->{"arg1"}->{"type"} && 
      exists $cond->{"arg2"}->{"type"} &&
      exists $cond->{"op"}) {
    if($cond->{"arg1"}->{"type"} eq "column" &&
       $cond->{"arg2"}->{"type"} eq "column" &&
       $cond->{"op"} eq "=") {
      push @$result, $cond;
    }
  } else {
    getJoins($cond->{"arg1"},$result);
    getJoins($cond->{"arg2"},$result);
  }
}

sub getAllCombinations {
  my ($npart, $curi, $curstr, $result) = @_;

  if (scalar(@$npart) == $curi ) {
    $curstr =~ s/^,//;
    push @$result, $curstr;
    return;
  }

  my $n = $npart->[$curi];
  for ( my $i=0; $i<$n; $i++ ) {
    getAllCombinations( $npart, $curi+1, "$curstr,$i", $result );
  }
}

# replaces table names with partition names
sub partitionizeSubquery {
  my ($tablename, $partition, $sq) = @_;

  for(my $i = 0; $i < (scalar(@{$sq->{"select"}})); $i++) {
    $sq->{"select"}->[$i] =~ s/\b$tablename\b/$partition/g;
  }

  for(my $i = 0; $i < (scalar(@{$sq->{"from"}})); $i++) {
    $sq->{"from"}->[$i] =~ s/\b$tablename\b/$partition/g;
  }

  replaceWhereOps($sq->{"where"}, $tablename, $partition);
}

sub replaceWhereOps {
  my ($rootptr, $old, $new) = @_;
  if (exists $rootptr->{"value"}) {
    if ($rootptr->{"type"} == "column") {
      $rootptr->{"value"} =~ s/\b$old\b/$new/g;
      $rootptr->{"fullorg"} =~ s/\b$old\b/$new/g;
    }
  } else {
    replaceWhereOps($rootptr->{"arg1"}, $old, $new);
    replaceWhereOps($rootptr->{"arg2"}, $old, $new);
  }
}

sub eliminateSubqueries {
  my ($sqsptr) = @_;
  my $i = 0;
  while($i < scalar(@$sqsptr)) {
    my $flag = 0;
    my @wexps = ();
    getWhereExps($sqsptr->[$i]->{"where"}, \@wexps);
    foreach my $exp (@wexps) {
      my ($arg1, $arg2) = ($exp->{"arg1"}, $exp->{"arg2"});
      if($arg1->{"type"} eq "column" && $arg2->{"type"} eq "column") {
        # join case
        my ($p1, $p1joinAttr) = split(/\./, $arg1->{"value"});
        my ($p2, $p2joinAttr) = split(/\./, $arg2->{"value"});
        my $t1 = substr $p1, 0, 1;
        my $t2 = substr $p2, 0, 1;
        my ($p1partType, $p1partAttr) = split(/:/, $tablepartkey{$t1});
        my ($p2partType, $p2partAttr) = split(/:/, $tablepartkey{$t2});
        my ($p1lo, $p1hi) = @{$part2range{$p1}};
        my ($p2lo, $p2hi) = @{$part2range{$p2}};
        if($p1partType eq $p2partType && $p1joinAttr eq $p2joinAttr &&
            $p1joinAttr eq $p1partAttr && $p2joinAttr eq $p2partAttr) {
          if($p1lo > $p2hi || $p2lo > $p1hi) {
            $flag = 1;
            last;
          }
        }
      }
      if($arg1->{"type"} eq "column" && $arg2->{"type"} eq "number") {
        my ($p1, $p1joinAttr) = split(/\./, $arg1->{"value"});
        my $t1 = substr $p1, 0, 1;
        my ($p1partType, $p1partAttr) = split(/:/, $tablepartkey{$t1});
        my ($p1lo, $p1hi) = @{$part2range{$p1}};
        my $op = $exp->{"op"};

        if($op eq ">") {
          if($arg2->{"value"} >= $p1hi) {
            $flag = 1;
            last;
          }
        } elsif($op eq "<") {
          if($arg2->{"value"} <= $p1lo) {
            $flag = 1;
            last;
          }
        } elsif($op eq "=") {
          if($arg2->{"value"} < $p1lo || $arg2->{"value"} > $p1hi) {
            $flag = 1;
            last;
          }
        } else {
          print "unknown operand: $op\n";
        }
      }
      if($arg1->{"type"} eq "number" && $arg2->{"type"} eq "column") {
        my $op = $exp->{"op"};
        my ($p2, $p2joinAttr) = split(/\./, $arg2->{"value"});
        my $t2 = substr $p2, 0, 1;
        my ($p2partType, $p2partAttr) = split(/:/, $tablepartkey{$t2});
        my ($p2lo, $p2hi) = @{$part2range{$p2}};

        if($op eq ">") {
          if($arg1->{"value"} <= $p2lo) {
            $flag = 1;
            last;
          }
        } elsif($op eq "<") {
          if($arg1->{"value"} >= $p2hi) {
            $flag = 1;
            last;
          }
        } elsif($op eq "=") {
          if($arg1->{"value"} < $p2lo || $arg1->{"value"} > $p2hi) {
            $flag = 1;
            last;
          }
        } else {
          print "unknown operand: $op\n";
        }
      }
    }
    if($flag) {
      splice @$sqsptr, $i, 1;
    } else {
      $i++;
    }
  }
}

sub getWhereExps {
  my ($rootptr, $result) = @_;

  if(exists $rootptr->{"arg1"}->{"type"} &&
      exists $rootptr->{"arg2"}->{"type"}) {
    push @$result, $rootptr;
  } else {
    getWhereExps($rootptr->{"arg1"}, $result);
    getWhereExps($rootptr->{"arg2"}, $result);
  }

}
